//给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。 
//
// 说明：拆分时可以重复使用字典中的单词。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
// 
//
// 示例 2： 
//
// 
//输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
//     注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 
//输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 300 
// 1 <= wordDict.length <= 1000 
// 1 <= wordDict[i].length <= 20 
// s 和 wordDict[i] 仅有小写英文字母组成 
// wordDict 中的所有字符串 互不相同 
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 
// 👍 1287 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class WordBreak {
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");wordDict.add("code");
        //wordDict.add("sand");wordDict.add("and");wordDict.add("cat");
        new WordBreak().new Solution().wordBreak(s, wordDict);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 这个用什么？我用dfs尝试了一下，一个字母一个字母的凑
     * 超时了妈的，所以说这种思路是可以的
     * 使用记忆化递归 memo存储以当前为起始单词的结果 1表示true 0表示false -1表示未赋值
     * 从0开始遍历时会1-len所有为下标开始的结果
     * 不进行记忆化的话 下标为1时会重复计算2-len的所有情况
     */
    class Solution {
        String s;
        List<String> wordDict;
        int[] memo;
        public boolean wordBreak1(String s, List<String> wordDict) {
            this.s = s;
            this.wordDict = wordDict;
            memo = new int[s.length()];
            Arrays.fill(memo, -1);
            return dfs(0);
        }

        private boolean dfs(int index) {
            if (index == s.length()) return true;
            if (memo[index]!=-1) return memo[index] != 0;
            for (int i = index; i < s.length() ; i++) {
                String t = s.substring(index, i+1);
                if (wordDict.contains(t)){
                    memo[index] = 1;
                    if (dfs(i+1)) return true;
                }
            }
            memo[index] = 0;
            return false;
        }

        /**
         * 使用动态规划解决问题
         * dp为一维数组，dp[i]表示字符串0-i能否组成单词
         * dp[i]是否为true需要进行联合判断
         * 取j<i，先判断s[0,j-1]是否为单词即dp[j]是否为true，再判断s[j,i]是否为单词
         */
        public boolean wordBreak2(String s, List<String> wordDict){
            int len = s.length();
            boolean[] dp = new boolean[len+1];
            dp[0] = true;//这里是保证边界的合理性（判断j=0开始到i-1是否为单词）
            for (int i = 1; i <= len ; i++) {
                for (int j = 0; j < i ; j++) {//这里从前向后从后向前无所谓的
                    if (dp[i]) break;//当前i已经赋值了，直接break
                    if (!dp[j]) continue;//当前j如果不是单词直接跳过
                    String substring = s.substring(j, i);
                    if (wordDict.contains(substring)) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[len];
        }

        /**
         * 二刷，使用的一维dp来做的
         */
        public boolean wordBreak(String s, List<String> wordDict) {
            boolean[] dp = new boolean[s.length()+1];
            dp[0] = true;//保证单个单词的匹配
            for (int j = 1; j <= s.length(); j++){//我这个方式一定要先遍历长度，再遍历单词，因为s中前边出现的单词后边可能再次出现
                for (String word : wordDict){
                    if (dp[j]) break; //跳到下一个长度，提高效率
                    if (j-word.length()<0) continue;//跳过不合理边界
                    String temp = s.substring(j-word.length(), j);//分割当前长度下的单词
                    dp[j] = (temp.equals(word) && dp[j-word.length()]);//看是否能匹配的上且之前的长度是否为true
                }
            }
            return dp[s.length()];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}














































